package demo.DataStrucAndAlgo.Linked;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/7/21-07-21-19:21
 * @Description：demo.DataStrucAndAlgo  链表：单向链表、双向链表、环形链表
 * 链表是有序列表，链式存储，结点包含data域，next域，各结点间不一定连续存储，
 * 链表从根节点有无存储数据可分为：带头链表（根节点有数据），不带头链表（根节点无数据）。
 * 链表的实现有很多结构：普通类，结构体，内部类...，数据遍历方式有循环，递归...
 */
class Node{       //结点类
    public int no;
    public String name;
    public Node next;        //保存下一个结点
    public Node( int no, String name){
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
class LinkedList{
    private  Node root = new Node(0,"");        //创建根节点
    public void add(Node newNode){         //普通add:不按序号存储
        Node temp = root;      //辅助结点
        while(true){           //查找链表最后结点
            if(temp.next == null){
                break;
            }
            temp = temp.next;       //向后一位
        }
        temp.next = newNode;        //添加结点
    }
    public void addByOrder(Node newNode){      //按(升序)顺序add
        Node temp = root;
        boolean flag = false;          //是否为重复编号
        while(true){
            if(temp.next == null){        //找到链表最后一位
                break;
            }
            if(temp.next.no > newNode.no){        //找到合适位置
                break;
            }
            if(temp.next.no == newNode.no){       //找到重复编号
                flag = true;
                break;
            }
            temp = temp.next;       //向后一位
        }
        if(flag){
            System.out.println("查找到重复数据，无法插入");
        }else{
            //插入新节点
            newNode.next = temp.next;
            temp.next = newNode;
        }

    }
    public void addByHead(Node newNode){       //将新结点插入为头结点
        newNode.next = root.next;
        root.next = newNode;
    }
    public void modify(Node newNode){         //根据Node中的no来匹配要修改的结点
        Node temp = root;
        boolean flag = false;    //判断是否找到了序号一样的Node
        while(true){
            if(temp.next == null){       //遍历完链表，未找到序号no一样的node结点
                break;
            }
            if(temp.next.no == newNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next.name = newNode.name;
        }else{
            System.out.println("没有找到要修改的结点");
        }
    }
    public void remove(int no){      //删除结点
        Node temp = root;
        boolean flag = false;       //判断是否找到了序号一样的Node
        while(true){
            if(temp.next == null){        //遍历完链表，没有找到
                break;
            }
            if(temp.next.no == no){       //找到了序号一样的
                flag = true;
                break;
            }
            temp = temp.next;        //后移一位
        }
        if(flag){
            temp.next = temp.next.next;       //删除结点
        }else{
            System.out.println("没有找到要删除的结点");
        }
    }
    public void reverseList() {
        if(root == null || root.next == null){
            return;
        }
        Node next;                //由于temp在拆结点时next会发生变化，所以得先保存一下
        Node temp=root.next;
        Node Newroot = new Node(0,"");    //新建翻转链表根节点

        while(temp!= null){
            next = temp.next;
            temp.next = Newroot.next;    //将结点从原链表拆下并与新链表的原先最前结点相连
            Newroot.next = temp;       //将拆下的结点与新链表的头结点相连
            temp = next;           //将原结点向后一位
        }
        root.next = Newroot.next;        //将翻转好的有效新链表接入原头结点之下
    }
    public void show(){
        if (root.next == null){         //判断是否为空链表
            System.out.println("链表为空");
            return;
        }
        Node temp = root;
        while(true){             //遍历打印
            if(temp.next == null){
                break;
            }
            System.out.println(temp.next.toString());
            temp = temp.next;
        }
    }
}
public class Linked_Common {         //单向链表_普通类
    public static void main(String[] args) {
        LinkedList link = new LinkedList();

        link.addByOrder(new Node(1,"小米"));
        link.addByOrder(new Node(3,"小明"));
        link.addByOrder(new Node(2,"小红"));
        System.out.println("按序号add： ");
        link.show();
        System.out.println("-----------------------------------");
        link.reverseList();
        link.show();

        link.modify(new Node(3,"小华"));
        link.show();

        link.remove(2);
        System.out.println("修改后：");
        link.show();
    }
}
